/**
 * @link https://leetcode.cn/problems/letter-combinations-of-a-phone-number/solutions/388738/dian-hua-hao-ma-de-zi-mu-zu-he-by-leetcode-solutio/?envType=study-plan-v2&envId=top-interview-150
 */
function letterCombinations(digits: string): string[] {
  let map: { [key: string]: string[] } = {
    "2": ["a", "b", "c"],
    "3": ["d", "e", "f"],
    "4": ["g", "h", "i"],
    "5": ["j", "k", "l"],
    "6": ["m", "n", "o"],
    "7": ["p", "q", "r", "s"],
    "8": ["t", "u", "v"],
    "9": ["w", "x", "y", "z"],
  };
  const traceback = (depth: number) => {
    if (depth === digits.length) return ans.push(tmp.join(""));
    map[digits[depth]].map((letter) => {
      tmp.push(letter);
      traceback(depth + 1);
      tmp.pop();
    });
  };
  let ans: string[] = [];
  let tmp: string[] = [];

  digits?.length && traceback(0);

  return ans;
}

/**
 * @link https://leetcode.cn/problems/combinations/?envType=study-plan-v2&envId=top-interview-150
 */
function combine(n: number, k: number): number[][] {
  const traceback = (index: number) => {
    if (tmp.length === k) {
      return ans.push(JSON.parse(JSON.stringify(tmp)));
    }
    for (let i = index; i < n + 1; i++) {
      tmp.push(i);
      //   console.log(tmp, depth);
      traceback(i + 1);
      tmp.pop();
    }
  };
  let ans: number[][] = [];
  let tmp: number[] = [];
  traceback(1);
  console.log(ans);

  return ans;
}

/**
 * @link https://leetcode.cn/problems/permutations/?envType=study-plan-v2&envId=top-interview-150
 */
function permute(nums: number[]): number[][] {
  const vis = Array(nums.length).fill(false);

  const traceback = (depth: number) => {
    // console.log(depth, [...tmp], [...vis]);

    if (nums.length === depth) {
      return ans.push([...tmp]);
    }
    for (let i = 0; i < nums.length; i++) {
      if (!vis[i]) {
        vis[i] = true;
        tmp.push(nums[i]);
        traceback(depth + 1);
        tmp.pop();
        vis[i] = false;
      }
    }
  };
  let ans: number[][] = [];
  let tmp: number[] = [];
  traceback(0);
  return ans;
}

/**
 * @link https://leetcode.cn/problems/combination-sum/?envType=study-plan-v2&envId=top-interview-150
 */
function combinationSum(candidates: number[], target: number): number[][] {
  const traceback = (index: number) => {
    console.log(tmp, [...tmpCandidates], index);

    if (tmp > target) {
      return;
    }
    if (tmp === target) {
      return ans.push([...tmpCandidates]);
    }

    for (let i = index; i < candidates.length; i++) {
      tmp += candidates[i];
      tmpCandidates.push(candidates[i]);
      traceback(i);
      tmp -= candidates[i];
      tmpCandidates.pop();
    }
  };

  let tmp = 0;
  let tmpCandidates: number[] = [];
  let ans: number[][] = [];
  traceback(0);
  console.log(ans);

  return ans;
}

/**
 * @link https://leetcode.cn/problems/generate-parentheses/?envType=study-plan-v2&envId=top-interview-150
 */
function generateParenthesis(n: number): string[] {
  const traceback = () => {
    console.log(left, right, tmp);

    if (left === 0 && right === 0) {
      return ans.push(tmp);
    }

    if (left > right) return;

    if (left) {
      left -= 1;
      tmp += "(";
      traceback();
      left += 1;
      tmp = tmp.slice(0, -1);
    }
    if (right) {
      right -= 1;
      tmp += ")";
      traceback();
      right += 1;
      console.log(tmp);

      tmp = tmp.slice(0, -1);
    }
  };

  let left: number = n;
  let right: number = n;
  let tmp = "";
  let ans: string[] = [];
  traceback();
  console.log(ans);

  return ans;
}

/**
 * @link https://leetcode.cn/problems/word-search/?envType=study-plan-v2&envId=top-interview-150
 */
function exist(board: string[][], word: string): boolean {
  const traceback = (i: number, j: number) => {
    console.log(i, j, visited, tmp, word.includes(tmp));

    if (word === tmp) return true;
    if (!word.includes(tmp)) return false;
    if (i >= board.length || i < 0 || j >= board[0].length || j < 0) {
      return false;
    }

    if (i - 1 >= 0 && !visited[i - 1][j]) {
      tmp += board[i - 1][j];
      visited[i - 1][j] = true;
      const f = traceback(i - 1, j);
      if (f) return true;
      tmp = tmp.slice(0, -1);
      visited[i - 1][j] = false;
    }

    if (i + 1 < board.length && !visited[i + 1][j]) {
      tmp += board[i + 1][j];
      visited[i + 1][j] = true;
      const f = traceback(i + 1, j);
      if (f) return true;
      tmp = tmp.slice(0, -1);
      visited[i + 1][j] = false;
    }
    if (j - 1 >= 0 && !visited[i][j - 1]) {
      tmp += board[i][j - 1];
      visited[i][j - 1] = true;
      const f = traceback(i, j - 1);
      if (f) return true;
      tmp = tmp.slice(0, -1);
      visited[i][j - 1] = false;
    }
    if (j + 1 < board[0].length && !visited[i][j + 1]) {
      tmp += board[i][j + 1];
      visited[i][j + 1] = true;
      const f = traceback(i, j + 1);
      if (f) return true;
      tmp = tmp.slice(0, -1);
      visited[i][j + 1] = false;
    }
  };
  let tmp: string = "";
  let visited = new Array(board.length);

  for (let i = 0; i < visited.length; i++) {
    visited[i] = [...new Array(board[0].length).fill(false)];
  }

  for (let i = 0; i < board.length; i++) {
    for (let j = 0; j < board[i].length; j++) {
      if (board[i][j] === word[0]) {
        console.log("start", i, j);
        tmp = board[i][j];
        visited[i][j] = true;

        const f = traceback(i, j);
        if (f) return true;
        visited[i][j] = false;
      }
    }
  }

  return false;
}

export default {
  letterCombinations,
  combine,
  permute,
  combinationSum,
  generateParenthesis,
  exist,
};
